import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 基数排序：又称“桶排序”
       适用范围：非负数的整数排序；
       特点：是经典的利用空间换时间的算法，速度很快，但是内存空间消耗很大
 */
public class BucketSortDemo {
    public static void main(String[] args) {
        //测试
        int[] ints = new int[]{53,3,542,748,14,214};
        System.out.println("排序前数组：");
        System.out.println(Arrays.toString(ints));
        //调用桶排序算法
        bucketSort(ints);
        System.out.println("排序后数组：");
        System.out.println(Arrays.toString(ints));
        System.out.println("---------------------------");

        //测试桶排序的时间复杂度
        //若处理80000个排序（八万个数据排序），需要花费多少时间? 本人电脑花费1秒
        //若处理800000个排序（八十万个数据排序），需要花费多少时间? 本人电脑花费1秒
        //若处理8000000个排序（八百万个数据排序），需要花费多少时间? 本人电脑花费1秒
        bucketSortTest();
    }

    //测试桶排序的时间复杂度
    //测试算法：若处理80000个排序，需要花费多少时间? 本人电脑花费1秒
    //测试算法：若处理800000个排序，需要花费多少时间? 本人电脑花费1秒
    //测试算法：若处理8000000个排序，需要花费多少时间? 本人电脑花费1秒
    public static void bucketSortTest(){
        int[] arr = new int[8000000];
        //先随机生成一个容量为80000个的数组
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random()*80000);
        }
        //创建 格式化日期格式对象：
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy.MM.dd HH:mm:ss");
        //创建当前时间的对象
        Date time1 = new Date();
        //对当前时间进行格式化
        String s1 = sdf.format(time1);
        //打印
        System.out.println("排序前时间："+s1);
        //进行排序
        bucketSort(arr);
        //再次创建当前时间对象
        Date time2 = new Date();
        String s2 = sdf.format(time2);
        System.out.println("排序后时间："+s2);
    }

    //桶排序算法
    public static void bucketSort(int[] arr){
        //1.先创建一个二维数组，模拟桶排序；其中每个一维数组，就表示一个桶
        // 说明 二维数组包含10个一维数组
        //     为了防止放入数的时候 数据溢出 ,则每一个一维数组的大小为array.length()
        //     很明显 空间换时间
        int[][] bucket = new int[10][arr.length];

        //2.定义一个一维数组，里面的值分别表示每个桶里面存放了多少个数，0-9的下标就是表示0-9个桶，每个下标对应的值就是相应桶存储数据的个数
        int[] bucketElementCounts = new int[10];

        //3.获取原数组中最大的数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        //4.获取最大数的位数，即，长度
        int maxLength = (max+"").length();

        //5.最大数有多少位，就要进行多少次桶排序
        for (int i = 0 , n = 1; i < maxLength; i++ , n *= 10) {
            //定义一个值，表示原数组头索引值，用于从桶中取出数据的时候，且第二次排序的时候，会自动归零，
            // 所以在需要定义在这个循环里面，而不是其他地方
            int index = 0;

            //6.每一次桶排序的时候，将原数组里面的每个数，都分别取出来，并按照特定顺序放入某个桶中
            for (int j = 0; j < arr.length; j++) {
                //根据数字的个位数（第二次排序就是十位，第三次就是百位，然后依次类推）
                int digitOfElement = arr[j] / n % 10;
                //分别放入对应的桶
                //bucketElementCounts[digitOfElement]，此时为0，因此可以用来作为桶数组的列值
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                //相应的桶标签数量需要加一，因为已经放入了一个数，数量必须加一
                bucketElementCounts[digitOfElement]++;
            }
            //7.每次桶排完序，都需要依次取出桶里面的数据，并放回原来的数组（即，覆盖原来的数组）
            //遍历所有的桶(总共只有十个桶)，若存在数据就依次取出来，放回原数组
            for (int j = 0; j < bucketElementCounts.length; j++) {
                //8.根据桶标签数量的值判断，是否有值需要取出
                if (bucketElementCounts[j] != 0) {
                    //9.若桶里面有数据，则遍历这个桶里面的所有数据，并取出来，放回原来的数组
                    for (int k = 0; k < bucketElementCounts[j]; k++) {
                        arr[index++] = bucket[j][k];
                    }
                    //10.当从记录桶标签数量的数组中，取出所有的值的时候，就要归零，方便下次循环的时候，重新计数，否则就会造成叠加错误
                    bucketElementCounts[j] = 0;
                }
            }
        }
    }
}
